import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 故我
 * Date: 2024-02-07
 * Time: 11:36
 */
public class MyHeap {
    public int[] array;
    public int useSize;

    public MyHeap() {
        array = new int[10];
    }

    // 初始化一个堆
    public void InitHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.array[i] = array[i];
            useSize++;
        }
    }

    // 创建一个堆
    public void createHeap() {
        for (int i = (useSize - 1 - 1) / 2; i >= 0; i--) {
            SiftDown(i, useSize);
        }
    }

    // 向下调整算法
    public void SiftDown(int parent, int useSize) {
        int child = 2 * parent + 1;
        while (child < useSize) {
            // 条件满足继续向下调整
            // 先选出左右孩子大孩子
            if (child + 1 < useSize && array[child] < array[child + 1]) {
                child = child + 1;
            }

            if (array[parent] < array[child]) {
                // 此时孩子节点大于父亲节点
                swap(parent, child);
                parent = child;
                child = 2 * parent + 1;
            } else {
                // 此时已经满足了大根堆条件
                break;
            }
        }
    }

    public void push(int val) {
        // 判断数组是否满了
        if (isFull()) {
            this.array = Arrays.copyOf(array, 2 * array.length);
        }
        // 直接往最后一个位置进行插入
        array[useSize] = val;
        SiftUp(useSize);
        useSize++;
    }

    public boolean isFull() {
        return this.array.length == useSize;
    }

    public void swap(int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 向下调整算法
     */
    public void SiftUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (array[child] > array[parent]) {
                swap(parent, child);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    /**
     * 堆的 pop 接口   最后一个元素与堆顶元素进行交换，再进行向下调整
     */
    public int pop() {
        if (isEmpty()) {
            throw new EmptyExeption("为空!");
        }
        int top = array[0];
        swap(0, useSize - 1);
        useSize--;
        SiftDown(0, useSize);
        return top;
    }

    public boolean isEmpty() {
        return useSize == 0;
    }

    /**
     * top-k 问题，建立一个为 k 的大根堆，小于堆顶的元素，才进入堆
     */
    public int[] TopK(int[] array, int k) {
        int[] ret = new int[k];
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Imp());//大根堆
        for (int i = 0; i < k; i++) {
            queue.offer(array[i]);
        }

        // 取后面元素
        for (int i = array.length - k; i < array.length; i++) {
            int top = queue.peek();
            if (array[i] < top) {
                queue.poll();
                queue.offer(array[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

    /**
     * 升序  建大堆，堆顶一定是最大的
     * 降序  建小堆  堆顶一定是最小的
     */

    public void HeapSort() {
        int end = useSize - 1;
        swap(0, end);
        SiftDown(0, useSize);
        end--;
    }

}
